home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / cagd_lib / cagdcmrg.c < prev    next >
C/C++ Source or Header  |  1995-12-30  |  18KB  |  469 lines
  1. /******************************************************************************
  2. * CagdCMrg.c - Curve/Point merging routines.                      *
  3. *******************************************************************************
  4. * Written by Gershon Elber, May 91.                          *
  5. ******************************************************************************/
  6.  
  7. #include "string.h"
  8. #include "cagd_loc.h"
  9.  
  10. static void CopyCrvOnCrv(CagdCrvStruct *DestCrv,
  11.              int Index,
  12.              CagdCrvStruct *SrcCrv);
  13. static void InterpolateLinearSeg(CagdCrvStruct *Crv, int Index1, int Index2);
  14.  
  15. /*****************************************************************************
  16. * DESCRIPTION:                                                               M
  17. * Merges two curves by connecting the end of Crv1 to the beginning of Crv2.  M
  18. *  If the end of Crv1 is identical to the beginning of Crv2 then the result  M
  19. * is as expected. However, if the curves do not meet their end points are    M
  20. * linearly interpolated if InterpolateDiscont is TRUE or simply blended out  M
  21. * in a freeform shape if If InterpolateDiscont is FALSE.                     M
  22. *                                                                            *
  23. * PARAMETERS:                                                                M
  24. *   Crv1:                 To connect to Crv1's starting location at its end. M
  25. *   Crv2:                 To connect to Crv2's end location at its start.    M
  26. *   InterpolateDiscont:   If TRUE, linearly interpolate discontinuity.       M
  27. *                                                                            *
  28. * RETURN VALUE:                                                              M
  29. *   CagdCrvStruct *:     The merged curve.                                   M
  30. *                                                                            *
  31. * KEYWORDS:                                                                  M
  32. *   CagdMergeCrvCrv, merge                                                   M
  33. *****************************************************************************/
  34. CagdCrvStruct *CagdMergeCrvCrv(CagdCrvStruct *Crv1,
  35.                    CagdCrvStruct *Crv2,
  36.                    int InterpolateDiscont)
  37. {
  38.     CagdBType CrvsSharePt;
  39.     int Length, Order, Len1, Len2;
  40.     CagdRType E3Pt1[3], E3Pt2[3];
  41.     CagdPointType CrvPType;
  42.     CagdCrvStruct *Crv;
  43.  
  44.     if (CAGD_IS_PERIODIC_CRV(Crv1) || CAGD_IS_PERIODIC_CRV(Crv2)) {
  45.     Crv1 = CnvrtPeriodic2FloatCrv(Crv1);
  46.     Crv2 = CnvrtPeriodic2FloatCrv(Crv2);
  47.     }
  48.     else {
  49.     Crv1 = CagdCrvCopy(Crv1);
  50.     Crv2 = CagdCrvCopy(Crv2);
  51.     }
  52.  
  53.     CagdMakeCrvsCompatible(&Crv1, &Crv2, TRUE, FALSE);
  54.     Order = Crv1 -> Order;
  55.     Len1 = Crv1 -> Length;
  56.     Len2 = Crv2 -> Length;
  57.  
  58.     /* Verify curve geometric types. */
  59.     switch (Crv1 -> GType) {
  60.     case CAGD_CBEZIER_TYPE:
  61.         Crv = CnvrtBezier2BsplineCrv(Crv1);
  62.         CagdCrvFree(Crv1);
  63.         Crv1 = Crv;
  64.         break;
  65.     case CAGD_CBSPLINE_TYPE:
  66.         break;
  67.     case CAGD_CPOWER_TYPE:
  68.         CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
  69.         break;
  70.     default:
  71.         CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  72.         break;
  73.     }
  74.  
  75.     switch (Crv2 -> GType) {
  76.     case CAGD_CBEZIER_TYPE:
  77.         Crv = CnvrtBezier2BsplineCrv(Crv2);
  78.         CagdCrvFree(Crv2);
  79.         Crv2 = Crv;
  80.         break;
  81.     case CAGD_CBSPLINE_TYPE:
  82.         break;
  83.     case CAGD_CPOWER_TYPE:
  84.         CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
  85.         break;
  86.     default:
  87.         CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  88.         break;
  89.     }
  90.  
  91.     /* Compute curve point types. */
  92.     CrvPType = Crv1 -> PType;
  93.  
  94.     /* Figure out if end point of Crv1 is equal to start point of Crv2 and   */
  95.     /* Compute the length of the resulting curve accordingly.             */
  96.     /* If the same point, then the result can omit one copy and therefore    */
  97.     /* has Len1 + Len2 - 1 Ctl points. If however a linear segment should be */
  98.     /* introduced between the two curves, it should hold Order colinear pts  */
  99.     /* including 2 end points shared with curves or Order - 2 new pts.       */
  100.     CagdCoerceToE3(E3Pt1, Crv1 -> Points, Len1 - 1, Crv1 -> PType);
  101.     CagdCoerceToE3(E3Pt2, Crv2 -> Points, 0, Crv2 -> PType);
  102.     CrvsSharePt = PT_APX_EQ(E3Pt1, E3Pt2);
  103.     Length = CrvsSharePt ? Len1 + Len2 - 1
  104.              : InterpolateDiscont ? Len1 + Len2 + Order - 2
  105.                           : Len1 + Len2;
  106.  
  107.     Crv = BspCrvNew(Length, Order, CrvPType);
  108.     CopyCrvOnCrv(Crv, 0, Crv1);
  109.     CopyCrvOnCrv(Crv, Length - Len2, Crv2);
  110.     InterpolateLinearSeg(Crv, Len1 - 1, Length - Len2);
  111.  
  112.     /* Update the knot vector. We assume open end condition here... */
  113.     CAGD_GEN_COPY(Crv -> KnotVector, Crv1 -> KnotVector,
  114.           (Len1 + Order - 1) * sizeof(CagdRType));
  115.     if (CrvsSharePt) {
  116.     CAGD_GEN_COPY(&Crv -> KnotVector[Len1 + Order - 1],
  117.               &Crv2 -> KnotVector[Order],
  118.               Len2 * sizeof(CagdRType));
  119.     BspKnotAffineTrans(&Crv -> KnotVector[Len1 + Order - 1],
  120.                Len2,
  121.                Crv -> KnotVector[Len1 + Order - 2] -
  122.                Crv2 -> KnotVector[0],
  123.                1.0);
  124.     }
  125.     else if (InterpolateDiscont) {
  126.     CAGD_GEN_COPY(&Crv -> KnotVector[Len1 + Order - 1],
  127.               &Crv2 -> KnotVector[1],
  128.               (Len2 + Order - 1) * sizeof(CagdRType));
  129.     BspKnotAffineTrans(&Crv -> KnotVector[Len1 + Order - 1],
  130.                Len2 + Order - 1,
  131.                Crv -> KnotVector[Len1 + Order - 2] -
  132.                Crv -> KnotVector[Len1 + Order - 1] + 1.0,
  133.                1.0);
  134.     }
  135.     else {
  136.     CAGD_GEN_COPY(&Crv -> KnotVector[Len1 + Order - 1],
  137.               &Crv2 -> KnotVector[Order - 1],
  138.               (Len2 + 1) * sizeof(CagdRType));
  139.     BspKnotAffineTrans(&Crv -> KnotVector[Len1 + Order - 1],
  140.                Len2 + 1,
  141.                Crv -> KnotVector[Len1 + Order - 2] -
  142.                Crv -> KnotVector[Len1 + Order - 1],
  143.                1.0);
  144.    
  145.     }
  146.  
  147.     CagdCrvFree(Crv1);
  148.     CagdCrvFree(Crv2);
  149.  
  150.     return Crv;
  151. }
  152.  
  153. /*****************************************************************************
  154. * DESCRIPTION:                                                               M
  155. * Merges a list of curves by connecting the end of one curve to the begining M
  156. * of the next. See also CagdMergeCrvCrv.                                     M
  157. *                                                                            *
  158. * PARAMETERS:                                                                M
  159. *   CrvList:              To connect into one curve.                         M
  160. *   InterpolateDiscont:   If TRUE, linearly interpolate discontinuity.       M
  161. *                                                                            *
  162. * RETURN VALUE:                                                              M
  163. *   CagdCrvStruct *:     The merged curve.                                   M
  164. *                                                                            *
  165. * KEYWORDS:                                                                  M
  166. *   CagdMergeCrvList, merge                                                  M
  167. *****************************************************************************/
  168. CagdCrvStruct *CagdMergeCrvList(CagdCrvStruct *CrvList, int InterpDiscont)
  169. {
  170.     if (CrvList != NULL && CrvList -> Pnext != NULL) {
  171.     CagdCrvStruct
  172.         *MergedCrv = CrvList;
  173.  
  174.     for (CrvList = CrvList -> Pnext;
  175.          CrvList != NULL;
  176.          CrvList = CrvList -> Pnext) {
  177.         CagdCrvStruct
  178.         *TmpCrv = CagdMergeCrvCrv(MergedCrv, CrvList,
  179.                       InterpDiscont);
  180.  
  181.         CagdCrvFree(MergedCrv);
  182.         MergedCrv = TmpCrv;
  183.     }
  184.     return MergedCrv;
  185.     }
  186.     else
  187.     return CrvList ? CagdCrvCopy(CrvList) : NULL;
  188. }
  189.  
  190. /*****************************************************************************
  191. * DESCRIPTION:                                                               M
  192. * Merges a curve and a point by connecting the end of Crv to Pt, using a     M
  193. * linear segment.                                                            M
  194. *                                                                            *
  195. * PARAMETERS:                                                                M
  196. *   Crv:          To connect to Pt its end.                     M
  197. *   Pt:           To connect to Crv's end point.                 M
  198. *                                                                            *
  199. * RETURN VALUE:                                                              M
  200. *   CagdCrvStruct *:     The merged curve.                                   M
  201. *                                                                            M
  202. * KEYWORDS:                                                                  M
  203. *   CagdMergeCrvPt, merge                                                    M
  204. *****************************************************************************/
  205. CagdCrvStruct *CagdMergeCrvPt(CagdCrvStruct *Crv, CagdPtStruct *Pt)
  206. {
  207.     CagdBType
  208.     CrvNew = FALSE,
  209.     IsRational = CAGD_IS_RATIONAL_CRV(Crv);
  210.     int i, NewLen, NewMaxCoord, Len,
  211.     Order = Crv -> Order,
  212.     PtMaxCoord = APX_EQ(Pt -> Pt[2], 0.0) ? 2 : 3,
  213.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  214.     CagdPointType CrvPType;
  215.     CagdRType t, **Points;
  216.     CagdCrvStruct *NewCrv, *TCrv;
  217.  
  218.     if (CAGD_IS_PERIODIC_CRV(Crv)) {
  219.     Crv = CnvrtPeriodic2FloatCrv(Crv);
  220.     CrvNew = TRUE;
  221.     }
  222.     Len = Crv -> Length;
  223.  
  224.     switch (Crv -> GType) {
  225.     case CAGD_CBEZIER_TYPE:
  226.         TCrv = CnvrtBezier2BsplineCrv(Crv);
  227.         if (CrvNew)
  228.         CagdCrvFree(Crv);
  229.         Crv = TCrv;
  230.         CrvNew = TRUE;
  231.         break;
  232.     case CAGD_CBSPLINE_TYPE:
  233.         break;
  234.     case CAGD_CPOWER_TYPE:
  235.         CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
  236.         break;
  237.     default:
  238.         CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  239.         break;
  240.     }
  241.  
  242.     /* Compute curve point types. */
  243.     NewMaxCoord = MAX(PtMaxCoord, MaxCoord);
  244.     CrvPType = CAGD_MAKE_PT_TYPE(IsRational, NewMaxCoord);
  245.  
  246.     /* A linear segment is added at the end with Order colinear pts.        */
  247.     /* However since first point is curve last point, only Order - 1 new.   */
  248.     NewLen = Len + Order - 1;
  249.  
  250.     NewCrv = BspCrvNew(NewLen, Order, CrvPType);
  251.     Points = NewCrv -> Points;
  252.  
  253.     CopyCrvOnCrv(NewCrv, 0, Crv);
  254.     for (i = 1; i <= NewMaxCoord; i++)
  255.     Points[i][NewLen - 1] = Pt -> Pt[i - 1];
  256.     if (IsRational)
  257.     Points[W][NewLen - 1] = 1.0;
  258.     InterpolateLinearSeg(NewCrv, Len - 1, NewLen - 1);
  259.  
  260.     /* Update the knot vector. We assume open end condition here... */
  261.     CAGD_GEN_COPY(NewCrv -> KnotVector, Crv -> KnotVector,
  262.           (Len + Order - 1) * sizeof(CagdRType));
  263.     t = Crv -> KnotVector[Len + Order - 1] + 1.0;
  264.     for (i = Len + Order - 1; i < NewLen + Order; i++)
  265.     NewCrv -> KnotVector[i] = t;
  266.  
  267.     if (CrvNew)
  268.     CagdCrvFree(Crv);
  269.  
  270.     return NewCrv;
  271. }
  272.  
  273. /*****************************************************************************
  274. * DESCRIPTION:                                                               M
  275. * Merges a point and a curve by connecting Pt to the starting point of Crv,  M
  276. * using a linear segment.                                                    M
  277. *                                                                            *
  278. * PARAMETERS:                                                                M
  279. *   Pt:           To connect to Crv's starting point.                 M
  280. *   Crv:          To connect to Pt its starting point.                 M
  281. *                                                                            *
  282. * RETURN VALUE:                                                              M
  283. *   CagdCrvStruct *:     The merged curve.                                   M
  284. *                                                                            M
  285. * KEYWORDS:                                                                  M
  286. *   CagdMergePtCrv, merge                                                    M
  287. *****************************************************************************/
  288. CagdCrvStruct *CagdMergePtCrv(CagdPtStruct *Pt, CagdCrvStruct *Crv)
  289. {
  290.     CagdBType
  291.     CrvNew = FALSE,
  292.     IsRational = CAGD_IS_RATIONAL_CRV(Crv);
  293.     int i, NewLen, NewMaxCoord, Len,
  294.     Order = Crv -> Order,
  295.     PtMaxCoord = APX_EQ(Pt -> Pt[2], 0.0) ? 2 : 3,
  296.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  297.     CagdPointType
  298.     CrvPType = CAGD_PT_E2_TYPE;
  299.     CagdRType t, **Points;
  300.     CagdCrvStruct *NewCrv, *TCrv;
  301.  
  302.     if (CAGD_IS_PERIODIC_CRV(Crv)) {
  303.     Crv = CnvrtPeriodic2FloatCrv(Crv);
  304.     CrvNew = TRUE;
  305.     }
  306.     Len = Crv -> Length;
  307.  
  308.     switch (Crv -> GType) {
  309.     case CAGD_CBEZIER_TYPE:
  310.         TCrv = CnvrtBezier2BsplineCrv(Crv);
  311.         if (CrvNew)
  312.         CagdCrvFree(Crv);
  313.         Crv = TCrv;
  314.         CrvNew = TRUE;
  315.         break;
  316.     case CAGD_CBSPLINE_TYPE:
  317.         break;
  318.     case CAGD_CPOWER_TYPE:
  319.         CAGD_FATAL_ERROR(CAGD_ERR_POWER_NO_SUPPORT);
  320.         break;
  321.     default:
  322.         CAGD_FATAL_ERROR(CAGD_ERR_UNDEF_CRV);
  323.         break;
  324.     }
  325.  
  326.     /* Compute curve point types. */
  327.     NewMaxCoord = MAX(PtMaxCoord, MaxCoord);
  328.     CrvPType = CAGD_MAKE_PT_TYPE(IsRational, NewMaxCoord);
  329.  
  330.     /* A linear segment is added at the end with Order colinear pts.        */
  331.     /* However since first point is curve last point, only Order - 1 new.   */
  332.     NewLen = Len + Order - 1;
  333.  
  334.     NewCrv = BspCrvNew(NewLen, Order, CrvPType);
  335.     Points = NewCrv -> Points;
  336.  
  337.     CopyCrvOnCrv(NewCrv, Order - 1, Crv);
  338.     for (i = 1; i <= NewMaxCoord; i++)
  339.     Points[i][0] = Pt -> Pt[i - 1];
  340.     if (IsRational)
  341.     Points[W][0] = 1.0;
  342.     InterpolateLinearSeg(NewCrv, 0, Order - 1);
  343.  
  344.     /* Update the knot vector. We assume open end condition here... */
  345.     CAGD_GEN_COPY(&NewCrv -> KnotVector[Order], &Crv -> KnotVector[1],
  346.           (Len + Order - 1) * sizeof(CagdRType));
  347.     t = Crv -> KnotVector[0] - 1.0;
  348.     for (i = 0; i < Order; i++)
  349.     NewCrv -> KnotVector[i] = t;
  350.  
  351.     if (CrvNew)
  352.     CagdCrvFree(Crv);
  353.  
  354.     return NewCrv;
  355. }
  356.  
  357. /*****************************************************************************
  358. * DESCRIPTION:                                                               M
  359. * Merges two points by connecting Pt1 to Pt2, using a linear segment.        M
  360. *                                                                            *
  361. * PARAMETERS:                                                                M
  362. *   Pt1, Pt2:     Two points to connect using a linear segment.              M
  363. *                                                                            *
  364. * RETURN VALUE:                                                              M
  365. *   CagdCrvStruct *:     The merged curve.                                   M
  366. *                                                                            M
  367. * KEYWORDS:                                                                  M
  368. *   CagdMergePtPt, merge                                                     M
  369. *****************************************************************************/
  370. CagdCrvStruct *CagdMergePtPt(CagdPtStruct *Pt1, CagdPtStruct *Pt2)
  371. {
  372.     CagdPointType
  373.     CrvPType = APX_EQ(Pt1 -> Pt[2], 0.0) && APX_EQ(Pt2 -> Pt[2], 0.0) ?
  374.                     CAGD_PT_E2_TYPE : CAGD_PT_E3_TYPE;
  375.     CagdCrvStruct
  376.     *Crv = BzrCrvNew(2, CrvPType);
  377.     CagdRType
  378.     **Points = Crv -> Points;
  379.  
  380.     Points[X][0] = Pt1 -> Pt[0];
  381.     Points[X][1] = Pt2 -> Pt[0];
  382.     Points[Y][0] = Pt1 -> Pt[1];
  383.     Points[Y][1] = Pt2 -> Pt[1];
  384.     if (CrvPType == CAGD_PT_E3_TYPE) {
  385.         Points[Z][0] = Pt1 -> Pt[2];
  386.         Points[Z][1] = Pt2 -> Pt[2];
  387.     }
  388.  
  389.     return Crv;
  390. }
  391.  
  392.  
  393. /*****************************************************************************
  394. * DESCRIPTION:                                                               *
  395. * Copies SrcCrv into DestCrv at point index Index.                 *
  396. *   DestCrv PType is assumed to hold Src PType.                     *
  397. *                                                                            *
  398. * PARAMETERS:                                                                *
  399. *   DestCrv:    Where the copied control points should go to.                *
  400. *   Index:      Index into DestCrv's control polygon.                        *
  401. *   SrcCrv:     Where the copied control points should come from.            *
  402. *                                                                            *
  403. * RETURN VALUE:                                                              *
  404. *   void                                                                     *
  405. *****************************************************************************/
  406. static void CopyCrvOnCrv(CagdCrvStruct *DestCrv,
  407.              int Index,
  408.              CagdCrvStruct *SrcCrv)
  409. {
  410.     CagdBType
  411.     IsNotRational = !CAGD_IS_RATIONAL_CRV(SrcCrv);
  412.     int i, j,
  413.     Len = SrcCrv -> Length,
  414.     MaxCoord = CAGD_NUM_OF_PT_COORD(SrcCrv -> PType);
  415.     CagdRType
  416.     **SrcPoints = SrcCrv -> Points,
  417.     **DestPoints = DestCrv -> Points;
  418.  
  419.     for (i = IsNotRational; i <= MaxCoord; i++)
  420.     CAGD_GEN_COPY(&DestPoints[i][Index], SrcPoints[i],
  421.               Len * sizeof(CagdRType));
  422.  
  423.     /* Fix the weights if source did not have them. */
  424.     if (IsNotRational && CAGD_IS_RATIONAL_CRV(DestCrv))
  425.     for (i = Index; i < Index + Len; i++)
  426.         DestPoints[W][i] = 1.0;
  427.  
  428.     /* Fix the higher coordinates (by coercing them to zero.) */
  429.     for (i = MaxCoord + 1; i <= CAGD_NUM_OF_PT_COORD(DestCrv -> PType); i++)
  430.     for (j = Index; j < Index + Len; j++)
  431.         DestPoints[i][j] = 0.0;
  432. }
  433.  
  434. /*****************************************************************************
  435. * DESCRIPTION:                                                               *
  436. * Linearly interpolates between the Crv points indices Index1 and Index2     *
  437. *                                                                            *
  438. * PARAMETERS:                                                                *
  439. *   Crv:            To add a linear segment between points of Index1 and     *
  440. *                   Index2.                             *
  441. *   Index1, Index2: Indices of first and last points that form the linear    *
  442. *                   segment.                                                 *
  443. *                                                                            *
  444. * RETURN VALUE:                                                              *
  445. *   void                                                                     *
  446. *****************************************************************************/
  447. static void InterpolateLinearSeg(CagdCrvStruct *Crv, int Index1, int Index2)
  448. {
  449.     CagdBType
  450.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  451.     int i, j,
  452.     DIndex = Index2 - Index1,
  453.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  454.     CagdRType
  455.     **Points = Crv -> Points;
  456.  
  457.     if (DIndex < 2)
  458.     return;                     /* No middle points to interp. */
  459.  
  460.     for (i = Index1 + 1; i < Index2; i++) {
  461.     CagdRType
  462.         t1 = ((CagdRType) (i - Index1)) / DIndex,
  463.         t2 = 1.0 - t1;
  464.  
  465.     for (j = IsNotRational; j <= MaxCoord; j++)
  466.         Points[j][i] = t2 * Points[j][Index1] + t1 * Points[j][Index2];
  467.     }
  468. }
  469.